We go beyond the notion of pairwise similarity and look into search problems with $k$-way similarity functions. We show that approximate $\mathcal{R} {3way}$ similarity search problems admit fast algorithms with provable guarantees, analogous to the pairwise case. Our analysis and speedup guarantees naturally extend to $k$-way resemblance. In the process, we extend traditional framework of \emph{locality sensitive hashing (LSH)} to handle higher order similarities, which could be of independent theoretical interest. The applicability of $\mathcal{R} {3way}$ search is shown on the Google sets" application. In addition, we demonstrate the advantage of $\mathcal{R} {3way}$ resemblance over the pairwise case in improving retrieval quality."